1474D - Cleaning - CodeForces Solution

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;

typedef long long int ll;
#define int ll
typedef pair<int, int> pii;

template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.first << ", " << p.second << ")"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
    cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) {
    cin >> p.first;
    return cin >> p.second;
}

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define forn(x) for(int i=0; i<x; i++)
#define wt(x) while(x--)
#define coutv(x) for(auto it: x) cout<<it<<" ";
#define coutvp(v) for(auto e : v) cout << e.first << " " << e.second << " "<<endl;
#define cina(arr, n) for(int i=0; i<n; i++) cin>>arr[i];
#define watch(x) cout << (#x) << " is " << (x) << endl
#define ii(x) int x; cin>>x;
#define li(x) ll x; cin>>x;
#define c2i(c) ((int)c-48)
#define pbv(v1, v2) for(auto it: v2) v1.push_back(it);
#define all(v) v.begin(), v.end()
#define tup tuple<int, int, int>
#define endl '\n'
#define MOD 1000000007

void solve(){
    int n; cin>>n;
    vector<int> v(n+1);
    for(int i=1; i<=n; i++) cin>>v[i];
    vector<int> dp(n+1);
    for(int i=1; i<=n; i++) dp[i] = v[i]-dp[i-1];
    int mn = *min_element(all(dp));
    if(mn>=0 && dp[n]==0){
        cout<<"YES"<<endl; return;
    }
    multiset<int> even, odd;
    for(int i=1; i<=n; i++){
        if(i%2) odd.insert(dp[i]);
        else even.insert(dp[i]);
    }
    odd.erase(odd.find(dp[1]));
    for(int i=0; i<=n-2; i++){
        if(dp[i]<0){
            break;
        }
        if(i%2==0){
            even.erase(even.find(dp[i+2]));
        }
        else{
            odd.erase(odd.find(dp[i+2]));
        }
        if(v[i+2]-dp[i]<0) continue;
        else if(v[i+1]-v[i+2]+dp[i]<0) continue;
        // correct
        int mn_odd = 1e18;
        int mn_even = 1e18;
        if(!odd.empty()) mn_odd = *odd.begin();
        if(!even.empty()) mn_even = *even.begin();
        if(i%2==0){
            int mnx1 = mn_even+2*v[i+1]-2*v[i+2];
            int mnx2 = mn_odd-2*v[i+1]+2*v[i+2];
            int f = 0;
            if(n%2==0){
                f = dp[n]+2*v[i+1]-2*v[i+2];
            }
            else f = dp[n]-2*v[i+1]+2*v[i+2];
            if(min(mnx1, mnx2)>=0 && f==0){
                cout<<"YES"<<endl;
                return;
            }
        }
        else{
            int mnx1 = mn_odd+2*v[i+1]-2*v[i+2];
            int mnx2 = mn_even-2*v[i+1]+2*v[i+2];
            int f = 0;
            if(n%2==0){
                f = dp[n]-2*v[i+1]+2*v[i+2];
            }
            else f = dp[n]+2*v[i+1]-2*v[i+2];
            if(min(mnx1, mnx2)>=0 && f==0){
                cout<<"YES"<<endl;
                return;
            }
        }
    }
    cout<<"NO"<<endl;
}

signed main(){
    fastio;
    int t; cin>>t;
    wt(t) solve();
}